<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>数据结构之散列</title>
</head>
<body>
  <script type="text/javascript">
    function HashTable() {
      this.table = new Array(137);
      this.simpleHash = simpleHash;
      this.betterHash = betterHash;
      this.buildChains = buildChains;
      this.put = put;
      this.get = get;
      this.showHashTable = showHashTable;
    }

    // 简单的散列函数，使用除留余数法
    function simpleHash(data) {
      var hash = 0;
      for (var i = 0; i < data.length; i++) {
        hash += data.charCodeAt(i);
      }
      return hash % this.table.length;
    }

    // 分布更均匀的散列函数
    function betterHash(data) {
      var H = 31; // 质数
      var hash = 0;
      for (var i = 0; i < data.length; i++) {
        hash += H * hash + data.charCodeAt(i);
      }
      if (hash < 0) {
        hash += this.table.length - 1;
      }
      return hash % this.table.length;
    }

    // 开链法
    function buildChains() {
      for (var i = 0; i < this.table.length; i++) {
        this.table[i] = new Array();
      }
    }

    // 插入数据
    function put(data) {
      var pos = this.simpleHash(data);
      this.table[pos] = data;

      // var pos = this.betterHash(data);
      // this.table[pos] = data;

      // 开链法
      // var pos = this.simpleHash(data);
      // var index = 0;
      // if (!this.table[pos][index]) {
      //   this.table[pos][index] = data;
      //   index++;
      // } else {
      //   while (this.table[pos][index]) {
      //     index++;
      //   }
      //   this.table[pos][index] = data;
      // }

      // 线性探测法
      // var pos = this.simpleHash(data);
      // if (!this.table[pos]) {
      //   this.table[pos] = data;
      // } else {
      //   while (this.table[pos]) {
      //     pos++;
      //   }
      //   this.table[pos] = data;
      // }
    }

    // 取出数据
    function get(data) {
      return this.table[this.simpleHash(data)];

      // 配合线性探测法
      // var pos = this.simpleHash(data);
      // console.log(data + '本来的位置是：' + pos);
      // for (var i = pos; i < this.table.length; i++) {
      //   if (this.table[i] === data) {
      //     return i;
      //   }
      // }
      // return -1;
    }

    // 打印整个散列表的数据
    function showHashTable() {
      var n = 0;
      for (var i = 0; i < this.table.length; i++) {
        if (this.table[i]) {
          console.log('键 ' + i + ' 对应的值是：' + this.table[i]);
        }
      }

      // 配合开链法
      // var n = 0;
      // for (var i = 0; i < this.table.length; i++) {
      //   if (this.table[i][0]) {
      //     console.log('键 ' + i + ' 对应的值是：' + this.table[i]);
      //   }
      // }
    }

    var hashTable = new HashTable();

    // 开链
    // hashTable.buildChains();

    hashTable.put('first');
    hashTable.put('study');
    hashTable.put('student');
    hashTable.put('cool');
    hashTable.put('ice');
    hashTable.put('china');
    hashTable.put('nicha');

    // console.log('使用线性探测法之后 nicha 的位置是：' + hashTable.get('nicha'));

    hashTable.showHashTable();
  </script>
</body>
</html>